package com.cat.chapter045;

/**
 * @author cat
 * @description https://www.nowcoder.com/practice/c552d3b4dfda49ccb883a6371d9a6932
 * @create 2025/7/14 10:42
 * @since JDK17
 */

public class Solution02 {

    int[] ans;
    static int MAXN = 100001;
    static int[][] trie = new int[MAXN][12];
    static int[] pass = new int[MAXN];
    static int cnt = 1;

    int parse(char c) {
        if (c == '#') {
            return 10;
        } else if (c == '-') {
            return 11;
        } else {
            return c - '0';
        }
    }

    void insert(String word) {
        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = parse(word.charAt(i));
            if (trie[cur][path] == 0) { // 没有
                trie[cur][path] = ++cnt;
            }
            cur = trie[cur][path];
            pass[cur]++;
        }
    }

    int count(String word) {
        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = parse(word.charAt(i));
            if (trie[cur][path] == 0) { // 断了
                return 0;
            }
            cur = trie[cur][path];
        }
        return pass[cur];
    }

    public int[] countConsistentKeys (int[][] b, int[][] a) {
        // write code here
        int m = b.length, n = a.length;
        ans = new int[m];

        for (int i = 0; i < n; i++) {   // 将所有字符串插入进去
            StringBuilder builder = new StringBuilder();
            int r = a[i].length;
            for (int j = 1; j < r; j++) {
                builder.append((a[i][j] - a[i][j - 1]) + "#");
            }
            insert(builder.toString());
        }

        for (int i = 0 ; i < m; i++) {
            StringBuilder builder = new StringBuilder();
            int r = b[i].length;
            for (int j = 1; j < r; j++) {
                builder.append((b[i][j] - b[i][j - 1]) + "#");
            }
            ans[i] = count(builder.toString());
        }
        return ans;
    }
}
